// sf_maze[栈] 迷宫动画效果

#include <bits/stdc++.h>
#include <unistd.h>
using namespace std;

#define PF(...) printf(__VA_ARGS__)
#define MAX_SIZE 128
vector<vector<int>> mapMaze = {
    {
        1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0,
    },
    {
        0, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    },
    {
        1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1,
    },
    {
        1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 1,
    },
    {
        1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1,
    },
    {
        1, 0, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1,
    },
    {
        0, 1, 1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1,
    },
    {
        1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0,
    },
    {
        0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0,
    },
    {
        1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1,
    },
    {
        1, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0,
    },
    {
        1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0,
    },
    {
        1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1,
    },
    {
        0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0,
    },
    {
        1, 0, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 1,
    },
    {
        1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 1,
    },
    {
        0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 1,
    },
    {
        1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0,
    },
    {
        0, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1,
    },
};

struct Postion {
  size_t _x = 0, _y = 0;
  bool operator==(const Postion other) const {
    return _x == other._x && _y == other._y;
  }
  Postion& operator+=(const pair<int, int>& dir) {
    _x += dir.first;
    _y += dir.second;
    return *this;
  }
  Postion operator+(const pair<int, int>& dir) {
    Postion p1;
    p1._x = _x + dir.first;
    p1._y = _y + dir.second;
    return p1;
  }
  void print() { printf("p:%d,%d\n", _x, _y); }
};

struct Stack {
  Postion* top;
  Postion* base;
};
Stack stk;

int stack_size() { return stk.top - stk.base; }

void stack_init() {
  stk.base = new Postion[MAX_SIZE];
  if (!stk.base) {
    return;
  }
  stk.top = stk.base;
}

void stack_push(Postion data) {
  // PF("push=%d,", stack_size()); data.print();
  if (!stk.base) {
    PF("stack ERROR\n");
    return;
  }
  if (stk.top - stk.base == MAX_SIZE) {
    PF("stack ERROR\n");
    return;
  }
  *(stk.top) = data;
  stk.top++;
}

Postion* stack_top() {
  if (stk.top - stk.base == 0) {
    PF("stack ERROR\n");
    return nullptr;
  }
  return stk.top - 1;
}

void stack_pop() {
  if (stk.top == stk.base) {
    PF("stack ERROR\n");
    return;
  }
  Postion p1 = *stack_top();
  // PF("pop=%d,", stack_size()); p1.print();
  stk.top--;
}

bool stack_empty() { return stk.top == stk.base; }

void stack_destory() {
  if (stk.base) {
    delete[] stk.base;
    stk.top = nullptr;
    stk.base = nullptr;
  }
}

void maze_set(Postion pos, int val) { mapMaze[pos._x][pos._y] = val; }
int maze_get(Postion pos) { return mapMaze[pos._x][pos._y]; }

void maze_addFence() {
  for (auto& vt : mapMaze) {
    vt.insert(vt.begin(), 0);
    vt.push_back(0);
  }
  vector<int> vtFence(mapMaze[0].size(), 0);
  mapMaze.insert(mapMaze.begin(), vtFence);
  mapMaze.push_back(vtFence);
}

void maze_print() {
  usleep(10 * 1000);
  system("cls");
  for (auto vt : mapMaze) {
    for (auto v : vt) {
      if (v == 0) {
        printf("■");
      } else if (v == 1) {
        printf("1 ");  //%d ", v%10);
      } else {
        printf("○");  // ○
      }
    }
    printf("\n");
  }
  printf("\n\n");
}

bool isVaildExit(Postion cur, Postion dest) {
  if (cur == dest) {
    return true;
  }
  return false;
}

//判断当前结点的下一个结点是否能走通-是不是可以走的点
//判断next是不是cur的下一个结点
//同一行相邻或者同一列相邻
//确实是cur的下一个结点相邻的
//判断这个点是不是在迷宫里
//合法坐标并且那个位置的值是1
//最后的参数==1，不仅仅是看是否是可以走的位置(道路是1)，
//同时有了这个我们就不用倒着往往前走了(不走重复的路)，不是有效的结点不只是墙(0)
//走过的也不是有效结点，直接pop出栈，通过出栈来往前回退
bool isNextPass(Postion cur, Postion next) {
  return mapMaze[next._x][next._y] == 1;
}

//寻找迷宫通路
int PassMaze(Postion enter, Postion dest) {
  vector<pair<int, int>> dirs = {
      {0, 1},
      {-1, 0},
      {0, -1},
      {1, 0},
  };
  stack_init();
  stack_push(enter);
  maze_set(enter, 2);
  maze_print();
  while (!stack_empty()) {
    Postion cur = *stack_top();
    if (cur == dest) {
      return stack_size();
    }
    bool bFindPath = false;
    for (auto di : dirs) {
      Postion next = cur + di;
      if (isNextPass(cur, next)) {
        stack_push(next);
        maze_set(next, maze_get(cur) + 1);
        maze_print();
        bFindPath = true;
        break;
      }
    }
    if (!bFindPath) {
      stack_pop();
    }
  }
  return -1;
}

int main55(void) {
  maze_addFence();
  maze_print();
  int ret = PassMaze({1, 1}, {19, 19});
  maze_print();
  if (ret > 0) {
    printf("have\n");
  } else {
    printf("no path\n");
  }
  return 0;
}
